package com.shm.jianxin;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param cars int整型一维数组 车辆数量
     * @param num int整型 出游总人数
     * @return int整型
     */
    public int carsTrans (int[] cars, int num) {
        // write code here
        if(num<1){
            return 0;
        }
        return help(cars,num,new int[num]);
    }

    public int help(int[] cars,int num,int[] count){
        if (num<0){
            return -1;
        }
        if (num==0){
            return 0;
        }
        if (count[num-1]!=0){
            return count[num-1];
        }
        int min = Integer.MAX_VALUE;
        for (int car : cars) {
            int ans = help(cars,num-car,count);
            if (ans>=0&&ans<min){
                min=ans+1;
            }
        }
        count[num-1]=(min==Integer.MAX_VALUE)?-1:min;
        return count[num-1];
    }
}